Semiconductor memory devices, including flash memory, typically utilize memory cells to store data as an electrical value, such as an electrical charge or voltage. A flash memory cell, for example, includes a single transistor with a floating gate that is used to store a charge representative of a data value. Flash memory is a non-volatile data storage device that can be electrically erased and reprogrammed. More generally, non-volatile memory (e.g., flash memory, as well as other types of non-volatile memory implemented using any of a variety of technologies) retains stored information even when not powered, as opposed to volatile memory, which requires power to maintain the stored information. Increases in storage density have been facilitated in various ways, including increasing the density of memory cells on a chip enabled by manufacturing developments, and transitioning from single-level flash memory cells to multi-level flash memory cells, so that two or more bits can be stored by each flash memory cell.
Non-volatile memory systems are often used to store a database of information, such as a database in which data objects and their attributes are stored. The database is typically organized and stored as a tiered data structure, for example a tree data structure (e.g., a B-tree) having nodes in which data objects, pointers to the data objects, and attributes of the data objects (sometimes called metadata) are stored. When writing an object and attributes of the object to the tiered data structure, for example in response to a host computer command, typical tiered data structure mapping algorithms require two I/O operations, one to write data and one to write updated metadata. Furthermore, when writing an object and N attributes of the object to the tiered data structure, typically N+2 nodes of the data structure (assuming the data object can be written in its entirety into a single node) would need to be updated, and thus rewritten, whereas the total amount of data to be written would typically be less than the total capacity of two (2) nodes. As a result, there is “write amplification” that is on the order of (N+2)/X, where X is the total amount of data to be written in units of nodes.